import java.util.*;

public class HJ16 {//购物车,0-1背包问题，需要动态规划
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int money = in.nextInt(); // 预算
        int n = in.nextInt(); // 物品数量
        Good[] goods = new Good[n + 1]; // 物品数组，索引从 1 开始

        // 初始化物品
        for (int i = 1; i <= n; i++) {
            int v = in.nextInt(); // 价格
            int p = in.nextInt(); // 重要性
            int q = in.nextInt(); // 主件ID（0 表示主件）
            goods[i] = new Good(v, p, q);
            if (q > 0) { // 如果是附件
                if (q <= n && goods[q] != null) { // 检查主件ID是否有效
                    if (goods[q].a1 == 0) {
                        goods[q].setA1(i); // 设置附件1
                    } else {
                        goods[q].setA2(i); // 设置附件2
                    }
                }
            }
        }

        // 动态规划数组
        int[] dp = new int[money + 1]; // dp[j] 表示预算为 j 时的最大满意度

        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            if (goods[i].q > 0) continue; // 跳过附件，只处理主件

            int v = goods[i].v; // 主件价格
            int p = goods[i].p; // 主件重要性
            int a1 = goods[i].a1; // 附件1 ID
            int a2 = goods[i].a2; // 附件2 ID

            // 计算四种情况的组合
            int v0 = v; // 只有主件
            int v1 = (a1 != 0) ? v + goods[a1].v : 0; // 主件 + 附件1
            int v2 = (a2 != 0) ? v + goods[a2].v : 0; // 主件 + 附件2
            int v3 = (a1 != 0 && a2 != 0) ? v + goods[a1].v + goods[a2].v : 0; // 主件 + 附件1 + 附件2

            // 计算四种情况的满意度
            int dp0 = v * p; // 只有主件
            int dp1 = (a1 != 0) ? dp0 + goods[a1].v * goods[a1].p : 0; // 主件 + 附件1
            int dp2 = (a2 != 0) ? dp0 + goods[a2].v * goods[a2].p : 0; // 主件 + 附件2
            int dp3 = (a1 != 0 && a2 != 0) ? dp0 + goods[a1].v * goods[a1].p + goods[a2].v * goods[a2].p : 0; // 主件 + 附件1 + 附件2

            // 动态规划更新
            for (int j = money; j >= 0; j--) {
                if (j >= v0) dp[j] = Math.max(dp[j], dp[j - v0] + dp0);
                if (j >= v1 && v1 != 0) dp[j] = Math.max(dp[j], dp[j - v1] + dp1);
                if (j >= v2 && v2 != 0) dp[j] = Math.max(dp[j], dp[j - v2] + dp2);
                if (j >= v3 && v3 != 0) dp[j] = Math.max(dp[j], dp[j - v3] + dp3);
            }
        }

        // 输出最大满意度
        System.out.println(dp[money]);
    }

    // 物品类
    static class Good {
        int v; // 价格
        int p; // 重要性
        int q; // 主件ID（0 表示主件）
        int a1 = 0; // 附件1 ID
        int a2 = 0; // 附件2 ID

        public Good(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }

        public void setA1(int a1) {
            this.a1 = a1;
        }

        public void setA2(int a2) {
            this.a2 = a2;
        }
    }
}